package EveryDay;

public class P2976 {
}

class P2976Test01{
    public long minimumCost(String source, String target, char[] original, char[] changed, int[] cost) {
        int len=source.length();
        int lenc=original.length;
        int costm=0;

        for(int i=0;i<len;i++){
            char c1=source.charAt(i);
            char c2=target.charAt(i);
            //查找目标元素的位置

            int[] resultA=searchRange(original, c1);
            //找到最小消费的值
            int costMin=Integer.MIN_VALUE;
            if(resultA[0]==-1){
                return -1;
            }

            for (int j = resultA[0]; j <= resultA[1]; j++) {
                //找到改变的范围
                int[] ints = searchRange(changed, original[i]);
                for (int k = ints[0]; k <= ints[1]; k++) {
                    if (cost[k] < costMin) {
                        costMin = cost[k];
                    }
                }
            }
            costm+=costMin;


        }

        return costm;
    }


    //二分查找
    public static int[] searchRange(char[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int[] result = {-1, -1};

        // 二分查找目标元素
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                result[0] = mid;
                result[1] = mid;
                break;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        // 如果未找到目标元素，直接返回
        if (result[0] == -1) {
            return result;
        }

        // 确定左边界
        int tempLeft = result[0];
        while (tempLeft >= 0 && nums[tempLeft] == target) {
            tempLeft--;
        }
        result[0] = tempLeft + 1;

        // 确定右边界
        int tempRight = result[1];
        while (tempRight < nums.length && nums[tempRight] == target) {
            tempRight++;
        }
        result[1] = tempRight - 1;

        return result;
    }
}